package nl.rug.jvleusen.datastructurelib.graph;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import nl.rug.jvleusen.datastructurelib.IGraph;

/**
 * @author Jeroen van Leusen
 * @see IGraph
 */
public class UnweightedUndirectionalGraph<E> implements IGraph<E> {

    private final List<Vertex<E>> vertices = new ArrayList<Vertex<E>>();

    /**
     * {@inheritDoc}
     */
    public boolean adjacent(E x, E y) {
        Vertex<E> vx = getVertexFor(x, vertices);

        if (vx == null) {
            return false;
        }

        return getVertexFor(y, vx.neighbors) != null;
    }

    /**
     * {@inheritDoc}
     */
    public List<E> neighbors(E x) {
        Vertex<E> vx = getVertexFor(x, vertices);

        if (vx == null) {
            return null;
        }

        List<E> result = new ArrayList<E>();
        for (Vertex<E> v : vx.neighbors) {
            result.add(v.data);
        }

        return result;
    }

    /**
     * {@inheritDoc}
     */
    public boolean add(E x, E y) {
        Vertex<E> vx = getVertexFor(x, vertices);
        Vertex<E> vy = getVertexFor(y, vertices);

        if (vx == null) {
            vx = new Vertex<E>(x);
            vertices.add(vx);
        }

        if (vy == null) {
            vy = new Vertex<E>(y);
            vertices.add(vy);
        }

        if (vx.neighbors.contains(vy)) {
            return false;
        } else {
            vx.neighbors.add(vy);
            vy.neighbors.add(vx);
            return true;
        }
    }

    /**
     * {@inheritDoc}
     */
    public boolean delete(E x, E y) {
        Vertex<E> vx = getVertexFor(x, vertices);

        if (vx == null) {
            return false;
        }

        Vertex<E> vy = getVertexFor(y, vertices);

        if (vx.neighbors.contains(vy)) {
            vx.neighbors.remove(vy);
            vy.neighbors.remove(vx);
            checkForDeadVertex(vx);
            checkForDeadVertex(vy);
            return true;
        } else {
            return false;
        }
    }

    /**
     * {@inheritDoc}
     */
    public boolean contains(E x) {
        return getVertexFor(x, vertices) != null;
    }

    /**
     * {@inheritDoc}
     */
    public Iterator<E> iterator() {
        return new Iterator<E>() {

            private Iterator<Vertex<E>> helper = vertices.iterator();

            public boolean hasNext() {
                return helper.hasNext();
            }

            public E next() {
                return helper.next().data;
            }

            public void remove() {
                throw new UnsupportedOperationException("Graphs do not support deletion by iterator.");
            }
        };
    }

    private Vertex<E> getVertexFor(E data, List<Vertex<E>> list) {
        if (data == null) {
            return null;
        }

        for (Vertex<E> v : list) {
            if (data.equals(v.data)) {
                return v;
            }
        }
        return null;
    }

    private void checkForDeadVertex(Vertex<E> vx) {
        if (vx.neighbors.isEmpty()) {
            vertices.remove(vx);
        }
    }

    private static class Vertex<E> {

        private final List<Vertex<E>> neighbors = new ArrayList<Vertex<E>>();
        private final E data;

        protected Vertex(E data) {
            this.data = data;
        }
    }
}
